package sort;

public class Heap 
{
int arr[];
	
	public Heap()
	{
		arr = new int[11];
	}
	
	private int getL(int i)
	{
		if(0 < 2*i && 2*i < arr.length)
			return arr[2*i];
		return 0;
	}
	
	private int getR(int i)
	{
		if(0 < 2*i+1 && 2*i+1 < arr.length)
			return arr[2*i+1];
		return 0;
	}
	
	public int getMin()
	{
		return arr[1];
	}
	
	
	private void print(int num, int level)
	{
		if(getL(num) != 0)
			print(2*num, level+1);
		
		for(int i = 0; i < level; i++)
			System.out.print("\t");
		
		System.out.println(arr[num]);
		
		if(getR(num) != 0)
			print(2*num+1, level+1);
	}
	
	public void insert(int num)
	{
		int i = arr.length-1;
		
		if(arr[i] != 0)
			makeNewArray();
		else
			while(arr[i] == 0 && i > 0) i--;
		arr[++i] = num;
		
		while(arr[i/2] > arr[i])
		{
			swap(i/2, i);
			i = i/2;
		}	
	}
	
	private void swap(int a, int b)
	{
		int tmp = arr[a];
		arr[a] = arr[b];
		arr[b] = tmp;
	}
	
	private void makeNewArray()
	{
		int mass[] = new int[ (int) (arr.length*3/2) ];
		for(int i = 0; i < arr.length; i++)
			mass[i] = arr[i];
		arr = mass;
	}
	
	public int remove()
	{
		int exitNum = arr[1];
		int i = arr.length-1;
		
		while(arr[i] == 0) i--;
		
		arr[1] = arr[i];
		arr[i] = 0;
		i = 1;
		
		while(arr[i] > getL(i) && getL(i) != 0 || arr[i] > getR(i) && getR(i) != 0)
			if(arr[i] > getL(i) && getL(i) != 0 && getL(i) < getR(i) && getR(i) != 0)
			{	
				swap(i, 2*i);
				i = 2*i;
			}
			else
			{
				swap(i, 2*i+1);
				i = 2*i+1;
			}
		
		return exitNum;
	}
	
	public static void main(String[] args) 
	{
		Heap tree = new Heap();
		
		for(int k = 0; k < 15; k++)	
			tree.insert((int)(Math.random()*10+1));
		
		tree.print(1,0);
		System.out.println("          "+"CHANGE before SORTING"+"              ");
		
		tree.remove();
		tree.print(1,0);
	}
}
